#ifndef SORT_HEAP_HPP
#define SORT_HEAP_HPP

#include "../common.hpp"

YFWZ100_NS_BEGIN

  // 调整为最大堆
  template <typename PointerLike>
  void heap_adjust(PointerLike a, int start, int length)
  {
    auto t = a[start];
    size_t left = 2 * start + 1;
    while (left < length) {
      size_t right = left + 1;
      if (right < length && a[left] < a[right]) {
        left = right;
      }
      if (a[start] < a[left]) {
        a[start] = a[left];
        start = left;
        left = 2 * start + 1;
      } else {
        break;
      }
      a[start] = t;
    }
  }

  // 建立一个最大堆
  template <typename PointerLike>
  void heap_build(PointerLike a, size_t length)
  {
    for (int i = (length - 1) / 2; i >= 0; i--) {
      heap_adjust(a, i, length);
    }
  }

  template <typename PointerLike>
  void heap_sort(PointerLike a, size_t length)
  {
    // 先建一个大堆
    heap_build(a, length);
    for (size_t i = length - 1; i > 0; i--) {
      swap(a[i], a[0]);
      // 通过弹堆把大堆顶的元素放到末尾，使得列表从小到大排序
      heap_adjust(a, 0, i);
    }
  }

YFWZ100_NS_END

#endif//SORT_HEAP_HPP
